import java.util.List;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class Test23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];

        ListNode newNode = new ListNode(-1);
        ListNode cur = newNode;
        boolean allNull;
        do{
            allNull = true;
            int min = 0;
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null){
                    allNull = false;
                    if (lists[min] == null){
                        min = i;
                        continue;
                    }
                    if (lists[i].val < lists[min].val){
                        min = i;
                    }
                }
            }
            cur.next = lists[min];
            if (lists[min] != null){
                lists[min] = lists[min].next;
            }
            cur = cur.next;
        }while (!allNull);

        return newNode.next;
    }
}
